Papers with probabilistic context-free grammar
A Fast Algorithm for Computing Prefix Probabilities (2023.acl-short)
Copied to clipboard
| Challenge: | Probabilistic context-free grammars are an important formalism in NLP . |
| Approach: | They propose to run a probabilistic context-free grammar in O(n3|N|3 + |N|4), where n is the input length and |N is the number of non-terminals in the grammar. |
| Outcome: | The proposed algorithm runs in O(n3|N|3 + |N|4), where n is the input length and |N | is the number of non-terminals in the grammar. |
Incremental Computation of Infix Probabilities for Probabilistic Finite Automata (D18-1)
Copied to clipboard
| Challenge: | Probabilistic finite automata are used to model distributions in natural language processing . a method that computes infix probabilities incrementally is proposed . |
| Approach: | They propose a method that computes infix probabilities incrementally for probabilistic finite automata . they propose to represent all the probabilities of matching strings as a series of transition matrix calculations . |
| Outcome: | The proposed method is theoretically faster than the previous method and better in practice. |
Circuit Compositions: Exploring Modular Structures in Transformer-Based Language Models (2025.acl-long)
Copied to clipboard
| Challenge: | Recent advances in mechanistic interpretability have made progress in identifying circuits, the minimal computational subgraphs responsible for a model’s behavior on specific tasks. |
| Approach: | They propose to analyze circuits for highly compositional subtasks within a transformer-based language model to determine their modularity and how they relate to each other. |
| Outcome: | The proposed approach shows that the circuits identified exhibit notable node overlap and cross-task faithfulness. |